/**
 *
 * @file
 *              kh.cpp
 *
 * @brief
 *              Heap implementation by khlamov
 */

#include "heap_kh.h"

heap_kh::heap_kh( size_t total, alloc_flags flag):heap876(total, flag, "kh"){
	//TODO:
	//test correctness input
	alloc_size = total;

	_heap = reinterpret_cast<void*>(new char[total]);
	//TODO:
	//catch exceptions from new
	push_list(_heap, total, true);
}

void heap_kh::push_list(void* v, size_t s, bool b) {
	pair<size_t, bool> temp1;
	temp1.first = s;	temp1.second = b;
	pair<void*, pair<size_t, bool>> temp2;
	temp2.first = v;	temp2.second = temp1;
	mem_list.push_back(temp2);
}

void* heap_kh::alloc( size_t sz, unsigned int tag ) {
	//vars
	list<pair<void*, pair<size_t, bool>>>::iterator itr = mem_list.begin();
	bool odd = true;
	size_t min = 0;
	if(sz % 2 == 0)
		odd = false;

	//find size of free space (min)
	while(itr != mem_list.end()) {
		if(itr->second.second && (itr->second.first >= sz)) {	//bool
			if(itr->second.first == sz) {
				min = sz;
				break;
			}
			if(odd) {
				if(itr->second.first % 2 == 1) {
					if(min) {
						min = min < itr->second.first?min:itr->second.first;
					} else {
						min = itr->second.first;
					}
				}
			} else {
				if(min) {
					min = min < itr->second.first?min:itr->second.first;
				} else {
					min = itr->second.first;
				}
			}
		}
		itr++;
	}

	//find iterator to free space
	itr = mem_list.begin();
	if(min) {
		while(itr != mem_list.end()) {
			if(itr->second.second) {	//bool
				if(itr->second.first == min)
					break;
			}
			itr++;
		}
	} else {
		while(itr != mem_list.end()) {
			if(itr->second.second && (itr->second.first >= sz))
				break;
			itr++;
		}
	}

	//if need free space exists
	if(itr == mem_list.end())
		return 0;

	//alloc memory
	if(itr->second.first != sz)
		push_list(reinterpret_cast<void*>(reinterpret_cast<char*>(itr->first)+sz), itr->second.first-sz, true);
	itr->second.first = sz;
	itr->second.second = false;

	void* res = itr->first;
	mem_list.sort();
	return res;

	return 0;
}
void heap_kh::free( void* ptr ) {
	list<pair<void*, pair<size_t, bool>>>::iterator itr = mem_list.begin();
	while(itr != mem_list.end()) {
		if(itr->first == ptr) {
			itr->second.second = true;

			//merge "free" records
			list<pair<void*, pair<size_t, bool>>>::iterator curr_itr = itr;
			bool flag_n = false;
			bool flag_c = false;
			if(curr_itr != mem_list.begin()) {
				itr--;
				if(itr->second.second){
					itr->second.first+=curr_itr->second.first;
					flag_c = true;
				}
			}
			if(curr_itr != mem_list.end()) {
				itr++;	itr++;
				if(itr->second.second){
					if(flag_c){
						curr_itr--;
						curr_itr->second.first+=itr->second.first;
						flag_n = true;
						curr_itr++;
					} else {
						curr_itr->second.first+=itr->second.first;
						flag_n = true;
					}
				}
			}

			itr = curr_itr;
			if(flag_c)
				itr = mem_list.erase(itr);
			else
				itr++;

			if(flag_n)
				mem_list.erase(itr);
			//

			break;
		}
		itr++;
	}
}

void heap_kh::prt() {
	list<pair<void*, pair<size_t, bool>>>::iterator itr = mem_list.begin();
	while(itr != mem_list.end()) {
		std::cout << itr->first << " " << itr->second.first << " " << itr->second.second << std::endl;
		itr++;
	}
	std::cout << "------" << std::endl;
}

heap_kh::~heap_kh(){
	delete [] _heap;
}

//TODO:
void heap_kh::free_all( unsigned int tag ){
	mem_list.clear();
	push_list(_heap, alloc_size, true);
}


size_t heap_kh::get_occupancy() const { return alloc_size; }
